{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Product After K Increments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumProduct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 次增加后的最大乘积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个非负整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。每次操作，你可以选择&nbsp;<code>nums</code>&nbsp;中 <strong>任一</strong>&nbsp;元素并将它 <strong>增加</strong>&nbsp;<code>1</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回 <strong>至多</strong>&nbsp;<code>k</code>&nbsp;次操作后，能得到的<em>&nbsp;</em><code>nums</code>的&nbsp;<strong>最大乘积</strong>&nbsp;。由于答案可能很大，请你将答案对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;取余后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [0,4], k = 5\n",
    "<b>输出：</b>20\n",
    "<b>解释：</b>将第一个数增加 5 次。\n",
    "得到 nums = [5, 4] ，乘积为 5 * 4 = 20 。\n",
    "可以证明 20 是能得到的最大乘积，所以我们返回 20 。\n",
    "存在其他增加 nums 的方法，也能得到最大乘积。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [6,3,3,2], k = 2\n",
    "<b>输出：</b>216\n",
    "<b>解释：</b>将第二个数增加 1 次，将第四个数增加 1 次。\n",
    "得到 nums = [6, 4, 3, 3] ，乘积为 6 * 4 * 3 * 3 = 216 。\n",
    "可以证明 216 是能得到的最大乘积，所以我们返回 216 。\n",
    "存在其他增加 nums 的方法，也能得到最大乘积。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length, k &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-product-after-k-increments](https://leetcode.cn/problems/maximum-product-after-k-increments/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-product-after-k-increments](https://leetcode.cn/problems/maximum-product-after-k-increments/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,4]\\n5', '[6,3,3,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans = ans * num % MOD\n",
    "        return ans                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapq.heapify(nums)\n",
    "        while k:\n",
    "            t = heapq.heappop(nums)\n",
    "            t += 1\n",
    "            heapq.heappush(nums, t)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for x in nums:\n",
    "            ans *= x\n",
    "            ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # if len(nums) < 2:\n",
    "        #     return nums[0] + k\n",
    "        # if max(nums) == min(nums):\n",
    "        #     n = len(nums)\n",
    "        #     a, b = k//n, k%n \n",
    "        #     res = 1\n",
    "        #     for i, num in enumerate(nums):\n",
    "        #         if i < b:\n",
    "        #             res *= num + a + 1\n",
    "        #         else:\n",
    "        #             res *= num + a\n",
    "        #         res = res % (10**9+7)\n",
    "        #     return res\n",
    "        # nums_heap = heapify(nums)\n",
    "        # while k:\n",
    "        #     a, b = heappop(nums), nums[0]\n",
    "        #     gap = max(1, b-a)\n",
    "        #     if gap >= k:\n",
    "        #         heappush(nums, a+k)\n",
    "        #         break \n",
    "        #     else:\n",
    "        #         heappush(nums, a+gap)\n",
    "        #         k -= gap\n",
    "        # res = 1 \n",
    "        # for num in nums:\n",
    "        #     res *= num \n",
    "        # return res % (10**9+7)\n",
    "\n",
    "        # -------------------------------------\n",
    "        MOD = 10**9 + 7\n",
    "        heapify(nums)\n",
    "        for _ in range(k):\n",
    "            num = heappop(nums)\n",
    "            heappush(nums, num+1)\n",
    "        res = 1 \n",
    "        for num in nums:\n",
    "            res *= num \n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return (nums[0] + k) % kmod\n",
    "\n",
    "        heapq.heapify(nums)\n",
    "\n",
    "        while k:\n",
    "            num = heapq.heappop(nums)\n",
    "            v = min(k, nums[0] - num)\n",
    "            v = max(v, 1)\n",
    "            k -= v\n",
    "            heapq.heappush(nums, num + v)\n",
    "\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans *= num\n",
    "            ans %= kmod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapq.heapify(nums)   # 建立最小堆\n",
    "        while k:\n",
    "            k -= 1\n",
    "            # 每次操作：弹出最小值，增加 1 并重新添加\n",
    "            num = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, num + 1)\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        for i in range(k):\n",
    "            heapreplace(nums,nums[0]+1)\n",
    "        ans = 1\n",
    "        for n in nums:\n",
    "            ans = ans*n%1000000007\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        for x in nums:\n",
    "            ans = ans * x % (10 ** 9 + 7)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        nums.append(float(\"inf\"))\n",
    "        for i in range(n):\n",
    "            tmp = (i + 1) * (nums[i + 1] - nums[i])\n",
    "            if k >= tmp:\n",
    "                k -= tmp\n",
    "                continue\n",
    "            d = k // (i + 1)\n",
    "            m = k % (i + 1)\n",
    "            for j in range(i + 1):\n",
    "                nums[j] = nums[i] + d\n",
    "                if j < m:\n",
    "                    nums[j] += 1\n",
    "            break\n",
    "        nums.pop()\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # nums.sort()\n",
    "        # n = len(nums)\n",
    "        # while k > 0:\n",
    "        #     if nums[0] != nums[1]:\n",
    "        #         t = min(nums[1] - nums[0] + 1, k)\n",
    "        #     else:\n",
    "        #         t = 1\n",
    "        #     nums[0] += t\n",
    "        #     k -= t\n",
    "        #     nums.sort()\n",
    "        # # print(nums)\n",
    "        # return reduce(lambda x, y: x * y, nums) % (10**9+7)\n",
    "\n",
    "        # 上面为用list实现的，下面参考题解用heapq优化\n",
    "        n = len(nums)\n",
    "        heapq.heapify(nums)\n",
    "        while k:  # 等价 while k > 0\n",
    "            a = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, a+1)\n",
    "            k -= 1\n",
    "        res = 1\n",
    "        mod = 10**9+7\n",
    "        for ele in nums:\n",
    "            res *= ele\n",
    "            res %= mod\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "\n",
    "        while k:\n",
    "            num = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, num + 1)\n",
    "            k -= 1\n",
    "\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans *= num\n",
    "            ans %= kmod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod=10**9+7\n",
    "        heapify(nums)\n",
    "        ans=1\n",
    "        while k>0:\n",
    "            heapreplace(nums,nums[0]+1)\n",
    "            k-=1\n",
    "        for x in nums:\n",
    "            ans= ans*x%mod\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapq.heapify(nums)   # 建立最小堆\n",
    "        while k:\n",
    "            k -= 1\n",
    "            # 每次操作：弹出最小值，增加 1 并重新添加\n",
    "            num = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, num + 1)\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= mod\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        end = 1\n",
    "        giao = 10 ** 9 + 7\n",
    "        heapq.heapify(nums)\n",
    "        for i in range(k):\n",
    "            num = heapq.heappop(nums)\n",
    "            heapq.heappush(nums,num + 1)\n",
    "        for i in nums:\n",
    "            end *= i\n",
    "            end %= giao\n",
    "        return end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # 最小堆，每次将最小的加1\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        for i in range(k):\n",
    "            nums[0] = nums[0] + 1\n",
    "            heapreplace(nums, nums[0])\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # nums.sort()\n",
    "        # n = len(nums)\n",
    "        # while k > 0:\n",
    "        #     if nums[0] != nums[1]:\n",
    "        #         t = min(nums[1] - nums[0] + 1, k)\n",
    "        #     else:\n",
    "        #         t = 1\n",
    "        #     nums[0] += t\n",
    "        #     k -= t\n",
    "        #     nums.sort()\n",
    "        # mod = 10**9+7\n",
    "        # return reduce(lambda x, y: x * y % mod, nums)\n",
    "\n",
    "        # 上面为用list实现的，下面参考题解用heapq优化\n",
    "        n = len(nums)\n",
    "        heapq.heapify(nums)\n",
    "        while k:  # 等价 while k > 0\n",
    "            a = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, a+1)\n",
    "            k -= 1\n",
    "        res = 1\n",
    "        mod = 10**9+7\n",
    "\n",
    "        # 1 所有元素乘完在mod, 会超时; 2 用reduce方法替代下面for循环,性能略差 \n",
    "        # for ele in nums:\n",
    "        #     res *= ele\n",
    "        #     res %= mod\n",
    "        # return res\n",
    "        return reduce(lambda x, y: x * y % mod, nums)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:  return nums[0] + k\n",
    "        \n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        preSum = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if k >= i * nums[i] - preSum:\n",
    "                preSum += nums[i]\n",
    "            else:\n",
    "                increase = (k + preSum - i * nums[i-1]) // i\n",
    "                cnt = (k + preSum - i * nums[i-1]) % i\n",
    "                ans = (nums[i-1] + increase + 1) ** cnt * (nums[i-1] + increase) ** (i-cnt) % MOD\n",
    "                for j in range(i, n):\n",
    "                    ans = (ans * nums[j]) % MOD\n",
    "                return ans\n",
    "        \n",
    "        k -= nums[-1] * n - preSum\n",
    "        increase = k // n\n",
    "        cnt = k % n\n",
    "        ans = (nums[-1] + increase + 1) ** cnt * (nums[-1] + increase) ** (n-cnt) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod=10**9+7\n",
    "        heapify(nums)\n",
    "        ans=1\n",
    "        while k>0:\n",
    "            heapreplace(nums,nums[0]+1)\n",
    "            k-=1\n",
    "        for i in range(len(nums)):\n",
    "            ans= ans*nums[i]%mod\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        count = len(nums)\n",
    "        remain = k\n",
    "\n",
    "        dp = [0] * count\n",
    "        cap = 0\n",
    "        flag_break = False\n",
    "        \n",
    "        for i in range(1, count):\n",
    "            dp[i] = dp[i-1] + (nums[i] - nums[i-1]) * i\n",
    "            if dp[i] > k:\n",
    "                cap = i-1\n",
    "                remain = k - dp[i-1]\n",
    "                flag_break = True\n",
    "                break\n",
    "        \n",
    "        if not flag_break:\n",
    "            cap = count-1\n",
    "            remain = k - dp[cap]\n",
    "        \n",
    "        d, m = divmod(remain, cap+1)\n",
    "\n",
    "        res = 1\n",
    "\n",
    "        for _ in range(m):\n",
    "            res *= nums[cap] + d + 1\n",
    "            res %= 1000000007\n",
    "\n",
    "        for _ in range(m, cap+1):\n",
    "            res *= nums[cap] + d\n",
    "            res %= 1000000007\n",
    "\n",
    "        for ind in range(cap+1, count):\n",
    "            res *= nums[ind]\n",
    "            res %= 1000000007\n",
    "\n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            k -= 1\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "        ans = 1\n",
    "        for x in nums:\n",
    "            ans = (ans * x) % (10 ** 9 + 7)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans = ans * num % MOD\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        def mull(x, y):\n",
    "            return x * y % MOD\n",
    "\n",
    "        heapify(nums)\n",
    "\n",
    "        while k:\n",
    "            heapreplace(nums, (nums[0] + 1))\n",
    "            k -= 1\n",
    "        \n",
    "        return reduce(mull, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        nums.append(inf)\n",
    "        n = len(nums)\n",
    "        # ans = 0\n",
    "        # print(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n - 1):\n",
    "            if (nums[i + 1] - nums[i]) * (i + 1) >= k:\n",
    "                d = k // (i + 1)\n",
    "                r = k % (i + 1)\n",
    "                # print(i, d, r)\n",
    "                tmp = (pow(nums[i] + d, i + 1 - r, mod) * pow(nums[i] + d + 1, r, mod)) % mod\n",
    "                # print(tmp)\n",
    "                for j in range(i + 1, n - 1):\n",
    "                    tmp = (tmp * nums[j]) % mod\n",
    "                return tmp\n",
    "            k -= (nums[i + 1] - nums[i]) * (i + 1)\n",
    "            # print(i, k)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans = (ans * num )% MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # for i in range(len(nums)):\n",
    "        #     nums[i] *= -1\n",
    "        out = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "        for i in nums:\n",
    "            out = out * i % mod\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while(k>0):\n",
    "            k-=1\n",
    "            ass=heapq.heappop(nums)\n",
    "            heapq.heappush(nums,ass+1)\n",
    "        ss=1\n",
    "        for i in nums:\n",
    "            ss*=i\n",
    "            if ss>(pow(10,9)+7):\n",
    "                ss=ss%(pow(10,9)+7)\n",
    "        return ss\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while k > 0:\n",
    "            top = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, top + 1)\n",
    "            k -= 1\n",
    "\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= 1000000007\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10**9 + 7  # 模数\n",
    "\n",
    "        # 初始化一个最小堆\n",
    "        heapq.heapify(nums)\n",
    "        \n",
    "        # 执行k次操作，每次都找到最小的数并加1\n",
    "        for _ in range(k):\n",
    "            smallest = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, smallest + 1)\n",
    "\n",
    "        # 计算最终的乘积\n",
    "        product = 1\n",
    "        for num in nums:\n",
    "            product = (product * num) % MOD\n",
    "\n",
    "        return product\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.maximumProduct([0, 4], 5))  # 输出应为 20\n",
    "print(sol.maximumProduct([6, 3, 3, 2], 2))  # 输出应为 216\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        s = k + nums[0]\n",
    "        m = 1\n",
    "        while m < n:\n",
    "            if s // m <= nums[m]:\n",
    "                break\n",
    "            s += nums[m]\n",
    "            m += 1\n",
    "        x = s // m\n",
    "        c = s % m\n",
    "        res = 1\n",
    "        for _ in range(m - c):\n",
    "            res = res * x % M\n",
    "        x += 1\n",
    "        for _ in range(c):\n",
    "            res = res * x % M\n",
    "        for i in range(m, n):\n",
    "            res = res * nums[i] % M\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        INT_MAX = 10**9 +7\n",
    "        ans = 1\n",
    "        while k!= 0:\n",
    "            heapreplace(nums, nums[0]+1)\n",
    "            k-= 1\n",
    "        for i in range(len(nums)):\n",
    "            ans = ans *nums[i] % INT_MAX\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while(k>0):\n",
    "            k-=1\n",
    "            heapq.heappush(nums,heapq.heappop(nums)+1)\n",
    "        ss=1\n",
    "        for i in nums:\n",
    "            ss*=i\n",
    "            if ss>(pow(10,9)+7):\n",
    "                ss=ss%(pow(10,9)+7)\n",
    "        return ss\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        mod = 10**9 + 7\n",
    "        for _ in range(k):\n",
    "            heapq.heapreplace(nums, nums[0] + 1)\n",
    "        ans = 1\n",
    "        for i in nums:\n",
    "            ans = ans * i % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums,nums[0] + 1)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans = ans * num % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while k>0:\n",
    "            heapq.heapreplace(nums, nums[0]+1)\n",
    "            k -=1\n",
    "        res = 1\n",
    "        for i in nums:\n",
    "            res *=i\n",
    "            res %= 1000000007\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        res = 1\n",
    "        while k:\n",
    "            x = heappop(nums)\n",
    "            heappush(nums, x + 1)\n",
    "            k -= 1\n",
    "        for x in nums:\n",
    "            res = (res * x) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:  return nums[0] + k\n",
    "        \n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        preSum = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if k >= i * nums[i] - preSum:\n",
    "                preSum += nums[i]\n",
    "            else:\n",
    "                increase = (k + preSum - i * nums[i-1]) // i\n",
    "                cnt = (k + preSum - i * nums[i-1]) % i\n",
    "                ans = (nums[i-1] + increase + 1) ** cnt * (nums[i-1] + increase) ** (i-cnt) % MOD\n",
    "                for j in range(i, n):\n",
    "                    ans = (ans * nums[j]) % MOD\n",
    "                return ans\n",
    "        \n",
    "        k -= nums[-1] * n - preSum\n",
    "        increase = k // n\n",
    "        cnt = k % n\n",
    "        ans = (nums[-1] + increase + 1) ** cnt * (nums[-1] + increase) ** (n-cnt) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        nums.append(float(\"INF\"))\n",
    "        # 遍历数组，优化模拟更新的过程\n",
    "        for i in range(n):\n",
    "            # 判断是否可以将数组下标 [0, i] 的元素更新为 nums[i+1]\n",
    "            tmp = (i + 1) * (nums[i+1] - nums[i])\n",
    "            if k >= tmp:\n",
    "                # 可以，则更新剩余的操作次数\n",
    "                k -= tmp\n",
    "                continue\n",
    "            # 不可以，则计算最终数组的元素\n",
    "            d = k // (i + 1)\n",
    "            m = k % (i + 1)\n",
    "            for j in range(i + 1):\n",
    "                nums[j] = nums[i] + d\n",
    "                if j < m:\n",
    "                    nums[j] += 1\n",
    "            break\n",
    "        nums.pop()\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # 贪心：从组最小值开始+1 == 下一个大的数\n",
    "        # 数据结构：最小堆，每次弹出最小值，加上值后放回去，再弹出最小值\n",
    "        heapq.heapify(nums)\n",
    "\n",
    "        while k > 0:\n",
    "            cur_min = heappop(nums)\n",
    "            cur_min += 1\n",
    "            heapq.heappush(nums,cur_min)\n",
    "            k -= 1\n",
    "\n",
    "        res = 1\n",
    "        mod = 10**9 + 7\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= mod\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod=10**9+7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums,nums[0]+1)\n",
    "            k-=1\n",
    "        ans=1\n",
    "        for i in range(len(nums)):\n",
    "            ans=ans*nums[i]%mod\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        m = len(nums)\n",
    "        nums.sort()\n",
    "        dp = [0]*m\n",
    "\n",
    "        # 初始化fin rem\n",
    "        fin = m-1\n",
    "        rem = k\n",
    "\n",
    "        # 寻找能一步抹平的右边界\n",
    "        for i in range(1,m):\n",
    "            dp[i] = (nums[i]-nums[i-1]) * i + dp[i-1]\n",
    "            if dp[i] > k:\n",
    "                fin = i-1\n",
    "                rem = k - dp[fin]\n",
    "                break\n",
    "\n",
    "        # 处理溢出边界\n",
    "        if dp[m-1]!=0 and dp[m-1] <= k:\n",
    "            fin = m-1\n",
    "            rem = k - dp[m-1]\n",
    "\n",
    "        # 用k的边角料 “撒胡椒面”\n",
    "        h = nums[fin] + rem//(fin+1)\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        # 第一块\n",
    "        for i in range(rem%(fin+1)):\n",
    "            ans *= (h+1)\n",
    "            ans %= 1000000007\n",
    "        \n",
    "        # 第二块\n",
    "        for i in range(rem%(fin+1), fin+1):\n",
    "            ans *= h\n",
    "            ans %= 1000000007\n",
    "        \n",
    "        # 第三块\n",
    "        for i in range(fin+1,m):\n",
    "            ans *= nums[i]\n",
    "            ans %= 1000000007\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        cnt= 1\n",
    "        for i in range(n-1):\n",
    "            if nums[i+1]>nums[i]:\n",
    "                if cnt*(nums[i+1]-nums[i])<=k:\n",
    "                    k -= cnt*(nums[i+1]-nums[i])\n",
    "                else:\n",
    "                    break\n",
    "            cnt += 1\n",
    "        mod = 10**9+7\n",
    "        if cnt == n:\n",
    "            val = nums[-1]+k//n\n",
    "            res = pow(val+1, k%n, mod)*pow(val, n-k%n, mod)\n",
    "            return res%mod\n",
    "        else:\n",
    "            val= nums[cnt-1]+k//cnt\n",
    "            res = pow(val, cnt-k%cnt, mod)*pow(val+1, k%cnt, mod)\n",
    "            for i in range(cnt, n):\n",
    "                res = (res*nums[i])%mod\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for x in nums:\n",
    "            ans = ans * x % (10**9 + 7)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) < 2:\n",
    "            return nums[0] + k\n",
    "        if max(nums) == min(nums):\n",
    "            n = len(nums)\n",
    "            a, b = k//n, k%n \n",
    "            # print(a, b, n)\n",
    "            res = 1\n",
    "            for i, num in enumerate(nums):\n",
    "                if i < b:\n",
    "                    res *= num + a + 1\n",
    "                else:\n",
    "                    res *= num + a\n",
    "                res = res % (10**9+7)\n",
    "            return res\n",
    "        nums_heap = heapify(nums)\n",
    "        while k:\n",
    "            a, b = heappop(nums), nums[0]\n",
    "            gap = max(1, b-a)\n",
    "            if gap >= k:\n",
    "                heappush(nums, a+k)\n",
    "                break \n",
    "            else:\n",
    "                heappush(nums, a+gap)\n",
    "                k -= gap\n",
    "        res = 1 \n",
    "        for num in nums:\n",
    "            res *= num \n",
    "        return res % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            x = heappop(nums)\n",
    "            heappush(nums, x+1)\n",
    "            k -= 1\n",
    "        \n",
    "        return reduce(lambda x, y:x*y % mod, nums) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "贪心策略，每次都给最小的数增加1\n",
    "'''\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans = ans * num % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        for _ in range(k):\n",
    "            tmp = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, tmp+1)\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= 10**9+7\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        heapq.heapify(nums)\n",
    "        n = len(nums)\n",
    "        ans = 1\n",
    "        for i in range(k):\n",
    "            heapq.heappush(nums, heapq.heappop(nums) + 1)\n",
    "        for i in range(n):\n",
    "            ans *= nums[i]\n",
    "            ans %= MOD\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while k:\n",
    "            a=heapq.heappop(nums)\n",
    "            heapq.heappush(nums,a+1)\n",
    "            k-=1\n",
    "        ans=1\n",
    "        for num in nums:\n",
    "            ans=(ans*num)%MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while(k>0):\n",
    "            k-=1\n",
    "            ass=heapq.heappop(nums)\n",
    "            heapq.heappush(nums,ass+1)\n",
    "        ss=1\n",
    "        for i in nums:\n",
    "            ss*=i\n",
    "            if ss>(pow(10,9)+7):\n",
    "                ss=ss%(pow(10,9)+7)\n",
    "        return ss\n",
    "    \n",
    "54\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapq.heapify(nums)\n",
    "        while k:\n",
    "            k -= 1\n",
    "            cur = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, cur + 1)\n",
    "        \n",
    "        ans = 1\n",
    "        for ch in nums:\n",
    "            ans *= ch\n",
    "            ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0] + k\n",
    "        # 每次选择最小的数增加，至少增加1，最多增加与第二小的数的差值或k\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            small = heappop(nums)\n",
    "            increase = min(nums[0] - small + 1, k)\n",
    "            k -= increase\n",
    "            heappush(nums, small + increase)\n",
    "        \n",
    "        ans = 1\n",
    "        for x in nums:\n",
    "            ans = ans * x % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        for x in nums:\n",
    "            print(x)\n",
    "            ans = ans * x % (10 ** 9 + 7)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        while k> 0 :\n",
    "            k -= 1\n",
    "            num = heapq.heappop(nums)\n",
    "            num += 1\n",
    "            \n",
    "            heapq.heappush(nums, num)\n",
    "        ans = 1 \n",
    "        while nums:\n",
    "            ans*= heapq.heappop(nums)\n",
    "            ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        heapify(nums)\n",
    "        for _ in range(k):\n",
    "            heapreplace(nums,nums[0]+1)\n",
    "        cnt=Counter(nums)\n",
    "        res = 1 \n",
    "        for k,v in cnt.items():\n",
    "            res *= pow(k,v,MOD)\n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        heapify(nums)\n",
    "        for _ in range(k):\n",
    "            heapreplace(nums,nums[0]+1)\n",
    "        cnt=Counter(nums)\n",
    "        res = 1 \n",
    "        for k,v in cnt.items():\n",
    "            res *= k**v\n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        h=[]\n",
    "        ans=1\n",
    "        for i in nums:\n",
    "            heapq.heappush(h,i)\n",
    "        for i in range(k):\n",
    "            x=heapq.heappop(h)\n",
    "            heapq.heappush(h,x+1)\n",
    "        for i in h:\n",
    "            ans*=i \n",
    "            ans%=(10**9+7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        q = []\n",
    "        for num in nums:\n",
    "            heapq.heappush(q, num)\n",
    "        while k:\n",
    "            cur = heapq.heappop(q)\n",
    "            heapq.heappush(q, cur + 1)\n",
    "            k -= 1\n",
    "        res = 1\n",
    "        for i in range(len(q)):\n",
    "            res *= q[i]\n",
    "            res %= int(1e9 + 7)\n",
    "        return res                                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # 将k次操作的每次操作都分给nums中最小的数，这样每次增加的乘积值为最大贪心\n",
    "        from heapq import heapify,heappush,heappop\n",
    "        pq=[x for x in nums]\n",
    "        heapify(pq)\n",
    "        for _ in range(k):\n",
    "            x=heappop(pq)\n",
    "            heappush(pq,x+1)\n",
    "        Mod=10**9+7\n",
    "        ans=1\n",
    "        for x in pq:\n",
    "            ans=ans*x%Mod\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        q = []\n",
    "        for num in nums:\n",
    "            heapq.heappush(q, num)\n",
    "        while k:\n",
    "            cur = heapq.heappop(q)\n",
    "            target = cur + k\n",
    "            if q and q[0] < target:\n",
    "                target = q[0] + 1\n",
    "            heapq.heappush(q, target)\n",
    "            k -= target - cur\n",
    "        res = 1\n",
    "        for i in range(len(q)):\n",
    "            res *= q[i]\n",
    "            res %= int(1e9 + 7)\n",
    "        return res                                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        que = queue.PriorityQueue()\n",
    "\n",
    "        for num in nums:\n",
    "            que.put(num)\n",
    "\n",
    "        while k > 0:\n",
    "            num = que.get()\n",
    "            que.put(num + 1)\n",
    "            k -= 1\n",
    "        \n",
    "        ans = 1 \n",
    "        \n",
    "        while not que.empty():\n",
    "            num = que.get()\n",
    "            ans *= num \n",
    "            ans %= int(1e9 + 7)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        l = len(nums)\n",
    "        h = []\n",
    "        for i in range(l):\n",
    "            heappush(h, nums[i])\n",
    "        for i in range(k):\n",
    "            tmp = heappop(h)\n",
    "            tmp += 1\n",
    "            heappush(h, tmp)\n",
    "        res = 1\n",
    "        for i in range(l):\n",
    "            res = (res*h[i]) % (1e9+7)\n",
    "        return int(res)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0] + k\n",
    "        Q = []\n",
    "        for x in nums:\n",
    "            heappush(Q, x)\n",
    "        while k > 0:\n",
    "            t = heappop(Q)\n",
    "            t += 1\n",
    "            heappush(Q, t)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        while Q:\n",
    "            ans = (ans * heappop(Q)) % (10 ** 9 + 7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        nums = SortedList(nums)\n",
    "        for _ in range(k):\n",
    "            t = nums[0]\n",
    "            nums.pop(0)\n",
    "            nums.add(t + 1)\n",
    "        ans = 1\n",
    "        for x in nums:\n",
    "            ans = ans * x % 1000000007\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        nums = SortedList(nums)\n",
    "        for i in range(k):\n",
    "            first = nums.pop(0)\n",
    "            nums.add(first + 1)\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans = ans * num % (10 ** 9 + 7)\n",
    "        return ans\n",
    "        # return math.prod(nums) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        cnt_dict = {}\n",
    "        for num in nums:\n",
    "            cnt_dict[num] = cnt_dict.get(num, 0) + 1\n",
    "        sorted_cnt = sorted(cnt_dict.items(), key=lambda d:d[0])\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        now = sorted_cnt[0][1]\n",
    "        for index in range(1, len(sorted_cnt)):\n",
    "            diff = sorted_cnt[index][0] - sorted_cnt[index - 1][0]\n",
    "            if diff * now <= k:\n",
    "                k -= diff * now\n",
    "                now += sorted_cnt[index][1]\n",
    "            else:\n",
    "                res = 1\n",
    "                for num, cnt in sorted_cnt[index:]:\n",
    "                    for _ in range(cnt):\n",
    "                        res = res * num % mod\n",
    "                \n",
    "                delta = k // now\n",
    "                k %= now\n",
    "                for _ in range(k):\n",
    "                    res = res * (sorted_cnt[index - 1][0] + delta + 1) % mod\n",
    "                for _ in range(k, now):\n",
    "                    res = res * (sorted_cnt[index - 1][0] + delta) % mod\n",
    "                \n",
    "                return res\n",
    "\n",
    "        res = 1\n",
    "        delta = k // now\n",
    "        k %= now\n",
    "        for _ in range(k):\n",
    "            res = res * (sorted_cnt[-1][0] + delta + 1) % mod\n",
    "        for _ in range(k, now):\n",
    "            res = res * (sorted_cnt[-1][0] + delta) % mod\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        ##每次对最小元素增加1\n",
    "        MOD=10**9+7\n",
    "        h=[[k,v] for k,v in Counter(nums).items()]\n",
    "        heapify(h)\n",
    "        while k>=h[0][1]:\n",
    "            theMin,count=heappop(h)\n",
    "            if h:\n",
    "                if h[0][0]==theMin+1:\n",
    "                    h[0][1]+=count\n",
    "                else:\n",
    "                    heappush(h,[theMin+1,count])\n",
    "                k-=count\n",
    "            else:\n",
    "                heappush(h,[theMin+k//count,count])\n",
    "                k%=count\n",
    "            # print(h,k)\n",
    "        ##此时对于h[i][0]，其中只能有k个加一\n",
    "        res=1\n",
    "        res=res*pow(h[0][0]+1,k,MOD)\n",
    "        res=res*pow(h[0][0],h[0][1]-k,MOD)\n",
    "        for j in range(1,len(h)):\n",
    "            res=res*pow(h[j][0],h[j][1],MOD)%MOD\n",
    "        return res%MOD\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
